package com.lecoboy.leecode;

import java.util.List;

/**
 * 链表反转
 */
public class InvertedListCase {
    class ListNode {
        int data;
        ListNode next;

        ListNode(int x) {
            data = x;
        }

        public String show() {
            return this.data + "->" + (this.next == null ? "NULL" : this.next.show());
        }
    }

    public static void main(String[] args) {
        InvertedListCase invertedListCase = new InvertedListCase();
        ListNode a = invertedListCase.new ListNode(1);
        ListNode b = invertedListCase.new ListNode(2);
        ListNode c = invertedListCase.new ListNode(3);
        ListNode d = invertedListCase.new ListNode(4);

        a.next = b;
        b.next = c;
        c.next = d;
        System.out.println(a.show());
        System.out.println(invertedListCase.reverseList(a).show());
    }


    /**
     * 链表反转
     * 方法：head的循环next，对prev进行尾插法
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        //尾插法
        while (head != null) {
            //当前节点
            ListNode cur = head;
            //头指针指向下一个，
            head = head.next;
            //当前节点尾结点指向当前节点，因为是尾插
            cur.next = prev;
            prev = cur;
        }
        return prev;
    }
}
